#include <cstdio>
#include <cmath>

struct Node
{
    int left, right;
    __int64 data;
    bool flag;
};

int n, pos;
Node h[ 100000 * 4 ];

void init( )
{
    int i, j;
    pos = 1;
    while ( pos < n ) pos <<= 1;
    for ( i = pos; i < pos + n; i++ )
    {
        scanf("%I64d", &h[ i ].data);
        h[ i ].left = h[ i ].right = i - pos;
        h[ i ].flag = false;
    }
    for ( i = pos + n; i < pos * 2; i++ )
    {
        h[ i ].left = h[ i ].right = i - pos;
        h[ i ].data = 0;
        h[ i ].flag = true;
    }
    for ( i = pos - 1; i >= 1; i-- )
    {
        h[ i ].left = h[ i * 2 ].left;
        h[ i ].right = h[ i * 2 + 1 ].right;
        h[ i ].data = h[ i * 2 ].data + h[ i * 2 + 1 ].data;
        h[ i ].flag = h[ i * 2 ].flag && h[ i * 2 + 1 ].flag;
    }
}

void decrease( int p, int left, int right )
{
    if ( left < h[ p ].left ) left = h[ p ].left;
    if ( right > h[ p ].right ) right = h[ p ].right;
    if ( left > h[ p ].right || right < h[ p ].left ) return ;
    if ( h[ p ].flag ) return ;
    if ( left == h[ p ].left && right == h[ p ].right )
    {
        if ( left == right )
        {
            h[ p ].data = int( sqrt( h[ p ].data ) );
            if ( h[ p ].data <= 1 ) h[ p ].flag = true;
            return ;
        }
    }
    decrease( p * 2, left, right );
    decrease( p * 2 + 1, left, right );
    h[ p ].data = h[ p * 2 ].data + h[ p * 2 + 1 ].data;
    h[ p ].flag = h[ p * 2 ].flag && h[ p * 2 + 1 ].flag;
}

__int64 query( int p, int left, int right )
{
    if ( left < h[ p ].left ) left = h[ p ].left;
    if ( right > h[ p ].right ) right = h[ p ].right;
    if ( left > h[ p ].right || right < h[ p ].left ) return 0;
    if ( left == h[ p ].left && right == h[ p ].right ) return h[ p ].data;
    return query( p * 2, left, right ) + query( p * 2 + 1, left, right );
}

void work( )
{
    int q, c, x, y, t;
    scanf("%d", &q);
    while ( q-- )
    {
        scanf("%d%d%d", &c, &x, &y); x--; y--;
        if ( x > y ) { t = x; x = y; y = t; }
        if ( c )
            printf("%I64d\n", query( 1, x, y ));
        else
            decrease( 1, x, y );
    }
}

int main( )
{
    int cas = 1;
    //freopen("in.txt", "r", stdin);
    while ( scanf("%d", &n) != EOF )
    {
        printf("Case #%d:\n", cas++);
        init( );
        work( );
        puts("");
    }
    return 0;
}
